The present invention relates to an encoding method and an encoding apparatus for multidimensionally coding information to be transmitted in a communication system. The present invention further relates to a decoding method and a decoding apparatus for iterative decoding of multidimensionally coded information. The encoding method, the encoding apparatus, the decoding method and the decoding apparatus of the present invention may be implemented in a communication unit of a communication system, e. g. a wireless telecommunication system.
During the transmission of information from a transmission unit to a receiving unit, e. g. from a base station to a mobile station of a wireless telecommunication system, errors may occur in disturbed transmission channels. These errors have to be detected and eventually corrected in the receiving unit. Channel coding is used to provide a possibility for the detection and correction of errors in the transmitted information. The channel code usually comprises additional error code symbols or error code bits, which are added to the information to be transmitted. These redundant error bits are transmitted with the information and are decoded on the receiving side, so that errors in the transmitted information can be detected and eventually corrected.
In order to provide a channel code, an encoding apparatus comprised in the transmission unit derives error code bits from the information bits by means of a corresponding coding method. On the receiving side, the error code bits enable to detect disturbed information bits. Depending on the size and the location of the error and the amount of error code bits it is eventually possible to correct the errors.
For such a channel coding, multiple encoding methods may be used. One of these encoding methods is the multidimensional coding. One of the multidimensional coding types are parallel concatenated systematic recursive codes, so-called turbo-codes, which are e. g. described in C. Berrou xe2x80x9cNear Shannon limit error-correcting and decoding:
Turbo-Codes (1)xe2x80x9d, Proc. ICC""93, May 1993.
Multidimensional codes are decoded on the receiving side by means of an iterative decoding processing. Thereby, a fixed number of iterations or iteration steps are performed to achieve a certain bit error rate or frame error rate. A fixed number of iterations or decoding loops, e. g. 8 or 16, is performed in the turbo decoding process to ensure a sufficient overall performance.
In FIG. 1, a known encoding structure of an encoding apparatus with a code rate of {fraction (1/3)} is shown. The input information is an encoded block of N bits, which are encoded in the encoding apparatus and output on three output lines. The known encoding apparatus shown in FIG. 1 generally consists of a first constituent encoder 1 and a second constituent encoder 2. The first constituent encoder 1 is provided with unchanged input information, whereas the second constituent encoder 2 is provided with input information processed in a turbo interleaving means 3.
The first constituent encoder 1 comprises a first delay means 4 and a second delay means 5. Both delay means 4 and 5 delay the respective input information by one bit. The unchanged input information supplied to the first constituent encoder 1 is input to the first delay means 4, delayed by one bit and then supplied to the second delay means 5 and there delayed by a further bit. The output signal from the second delay means 5 is fed back and added to the unchanged input information and the output signal of the first delay means 4 in an adding means 6. The output signal from the adding means 6 is supplied to the delay means 4 as well as to an adding means 7. In the adding means 7, the output signal from the adding means 6 is added to the output signal of the second delay means 5. The output signal of the adding means 7 is the second output (output 1) of the shown turbo encoding apparatus.
The input information of the encoding apparatus shown in FIG. 1 is further supplied to a turbo interleaving means 3, where the information bits are interleaved and then supplied to a second constituent encoder 2. The input information of the second constituent encoder 2 is supplied to a first delay means 8, delayed by one bit, supplied to a second delay means 9 and delayed by a second bit there. The output signal from the second delay means 9 is fed back to an adding means 10, in which the output signal from the first delay means 8, and the output signal from the turbo interleaving means 3 and the output signal from the second delay means 9 are added. The output signal from the adding means 10 is the input of the first delay means 8. The output signal of the second delay means 9 is further fed to an adding means 11, in which it is added to the output signal of the adding means 10 to provide the third output signal (output 2) of the shown encoding apparatus.
The first output signal (output 0) of the encoding apparatus shown in FIG. 1 is the unchanged input information.
The three output signals of the encoding apparatus shown in FIG. 1 are then further processed and transmitted in a transmission channel to a receiving apparatus, in which they are turbo decoded, e. g. by a turbo decoding apparatus 12 as shown in FIG. 2. The known turbo decoding apparatus 12 shown in FIG. 2 is supplied with three input signals corresponding to the three output signals of the known encoding apparatus shown in FIG. 1. The received information bits, which correspond to the first output signal of the encoding apparatus of FIG. 1 are the unchanged information bits, which are fed to a first constituent decoder 13 of the turbo decoding apparatus 12. The received parity bits of the first code are soft parity information, which are also supplied to the first constituent decoder 13, correspond to the second output (output 1) of the encoding apparatus of FIG. 1. The received parity bits of the second code are soft parity information, which are fed to the second constituent decoder 14 of the turbo decoding apparatus 12 correspond to the third output (output 2) of the encoding apparatus shown in FIG. 1. The second output (output 1) and the third output (output 2) of the encoding apparatus of FIG. 1 are therefore error code bits (parity bits), which are transmitted together with the unchanged information bits to provide an error code, which is used on the receiving side to detect and eventually correct errors in the transmitted information signal (output 0).
The received parity bits of the first code and the received information bits are supplied to the first constituent decoder 13 of the turbo decoding apparatus 12 and processed to provide decoded soft decision values, which are supplied to and processed in a deinterleaver 15. The deinterleaved soft decision values from the deinterleaver 15 are supplied to the second constituent decoder 14 of the turbo decoder apparatus 12. The received information bits are further supplied to an interleaver 16. The interleaved information bits from the interleaver 16 are also supplied to the second constituent decoder 14. The received parity bits of the second code are supplied to the second constituent decoder 14. In the second constituent decoder 14, the three input signals are decoding processed. The output signal from the second constituental decoder 14 comprises soft decision values, which are fed back to an deinterleaver 18. The deinterleaved soft decision values from the deinterleaver 18 are fed back and supplied to the first constituent decoder 13.
In the known turbo decoding apparatus 12 shown in FIG. 2, the number of iterations through the deinterleaver 18 is a fixed number of iterations, e. g. 8 or 16 to provide a sufficient overall performance in terms of the bit error rate or frame error rate. Thereby, in each iteration step, the second constituent decoder improves the soft decision likelihood values of the first constituent decoder 13 and the deinterleaver 15. In each iteration step, the soft decision likelihood values are therefore changed and improved to improve the performance in term of the bit error rate and the frame error rate. After a predetermined fixed number of iteration steps, the soft decision likelihood values output from the second constituent decoder 14 are supplied to a deinterleaver 17. The deinterleaved soft decision likelihood values from the deinterleaver 17 are supplied to a hard decision means 19, in which the soft decision likelihood values are transformed into hard decision values, e. g. bits of the values xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to provide an output signal. Since always the same high number of iteration steps is performed, the computational load and thus the power consumption and also the processing delay, since each iteration loop needs a certain processing time, are very high.
One proposal to determine an adaptive stop criteria in iterative decoding of multidimensionally decoded information is described in EP 0 755 122 A2. In this proposed structure, a comparison of the soft decision values output from the second constituent decoder after each iteration step with the soft decision values of the immediately preceding iteration step is performed. If the soft decision values between two immediately succeeding iteration steps do not change, the decoding iteration is stopped. However, if the transmitted information bits are erroneous, this proposed method does not provide a possibility to detect and correct errors. Further, always one iteration step more than needed is performed, since the proposed stop criteria requires that two succeeding iteration steps result in the same soft decision likelihood values.
The object of the present invention is therefore to provide an encoding apparatus, an encoding method, a decoding apparatus and a decoding method, which enable an optimized and effective iterative decoding of multidimensionally coded information.
This object is achieved by a decoding apparatus according to claim 1, a decoding method according to claim 8, an encoding apparatus according to claim 9 and an encoding method according to claim 11.
The decoding apparatus for iterative decoding of multidimensionally encoded information according to the present invention comprises means for performing at least one decoding iteration on multidimensionally coded information, and means for checking the decoded information after each decoding iteration and for causing said decoding iteration means to perform a further decoding iteration on the basis of a checking result. The decoding method for iterative decoding of multidimensionally coded information according to the present invention comprises the steps of performing at least one decoding iteration on multidimensionally coded information, and checking the decoded information after each decoding iteration step and for causing a further decoding iteration to be performed on the basis of a checking result.
The encoding apparatus according to the present invention comprises means for generating a checksum for incoming data, means for constructing frames on the basis of said incoming data and said generated checksum, and means for multidimensionally coding said frames.
The encoding method according to the present invention comprises the steps of generating a checksum for incoming data, constructing frames on the basis of said incoming data and said generated checksum, and multidimensionally coding said frames.
The present invention therefore provides an encoding apparatus and method and a decoding apparatus and means, which enable an optimized and effective iterative decoding of multidimensionally coded information. Particularly, no more decoding iteration steps are performed if the information has been decoded correctly. Thereby, the mean number of iteration steps is reduced without sacrificing the performance of the turbo decoding. The reduction of the iteration steps ensures less computational complexity and less processing delay, whereby at the same time the decoding performance is maintained. Since the maximum numbers of iteration steps in the decoding processing can still be fixed, the overall performance in terms of the bit error rate and the frame error rate is the same as in the state of the art, however, the mean number of iteration steps is reduced dramatically. This is particularly due to the fact that many transmitted data frames can be decoded and corrected completely with a much less number of iteration steps compared to the maximum possible number of iteration steps.
Advantageously, the checking means of the decoding apparatus according to the present invention comprises an error detection means for detecting an error in said decoded information. In this case, the multidimensionally coded information may comprise a cyclic redundancy checksum, whereby said error detection means performs a cyclic redundancy check on said decoded information. Thereby, a small cyclic redundancy checksum might be appended to each information frame.
Alternatively, the checking means of the decoding apparatus according to the present invention may comprise an error detection and correction means for performing an error detection and correction on said decoded information. This construction is very effective in correcting bit errors in the transmitted information even if the decoding iteration means was not able to correct all errors even after the maximum number of decoding iteration steps.
Further advantageously, the checking means provide a control signal for causing said decoding iteration means to perform another iteration if the checking result is negative. Thus, the decoding iteration means only performs one iteration at a time and is controlled or triggered by a control signal from the checking means to continue the decoding processing in case that the checking result indicates, that the decoded information are not yet correct.
The means for performing at least one decoding iteration on multidimensionally coded information in the decoding apparatus of the present invention is preferably a decoding means known in the state of the art, so that the decoding apparatus according to the present invention can be built in a simple and effective way using a known decoding iteration means.
Further advantageously, the decoding apparatus according to the present invention comprises a counting means for counting the number of decoding iteration steps performed by said decoding iteration means and for causing decoded information to be output if a predetermined maximum number of iteration steps is reached even if said checking result is negative. In other words, the maximum number of decoding iteration steps is limited to a predetermined maximum number. The checking result of the decoded information, which usually are soft decision likelihood values, can still be used in a further stage of the processing, since a reliability value of the decoded information is provided by the checking result, even if the checking result is negative. On the basis of this reliability information, one of the next stages of the processing of the information can decide how to deal with the corresponding information data frame still containing errors.
Further advantageously, the decoding apparatus according to the present invention comprises means for extracting data from said decoded information if said checking result is positive and for outputting said extracted data. If, e. g. the decoded information contain a checksum appended to the transmission data, the checksum data are removed and the information data of interest are extracted to be further processed.
In the encoding apparatus of the present invention, the checksum generating means advantageously generates a checksum for a cyclic redundancy check. New data frames are then constructed using the original incoming data bits and the generated cyclic redundancy check bits. Although this creates some overhead, this overhead is very small and is used on the receiving side to significantly reduce the power consumption and the computational complexity.